home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / test / test_bisect.py < prev    next >
Encoding:
Python Source  |  2005-10-18  |  8.9 KB  |  244 lines
  1. import unittest
  2. from test import test_support
  3. from bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
  4. from UserList import UserList
  5.  
  6. class TestBisect(unittest.TestCase):
  7.  
  8.     precomputedCases = [
  9.         (bisect_right, [], 1, 0),
  10.         (bisect_right, [1], 0, 0),
  11.         (bisect_right, [1], 1, 1),
  12.         (bisect_right, [1], 2, 1),
  13.         (bisect_right, [1, 1], 0, 0),
  14.         (bisect_right, [1, 1], 1, 2),
  15.         (bisect_right, [1, 1], 2, 2),
  16.         (bisect_right, [1, 1, 1], 0, 0),
  17.         (bisect_right, [1, 1, 1], 1, 3),
  18.         (bisect_right, [1, 1, 1], 2, 3),
  19.         (bisect_right, [1, 1, 1, 1], 0, 0),
  20.         (bisect_right, [1, 1, 1, 1], 1, 4),
  21.         (bisect_right, [1, 1, 1, 1], 2, 4),
  22.         (bisect_right, [1, 2], 0, 0),
  23.         (bisect_right, [1, 2], 1, 1),
  24.         (bisect_right, [1, 2], 1.5, 1),
  25.         (bisect_right, [1, 2], 2, 2),
  26.         (bisect_right, [1, 2], 3, 2),
  27.         (bisect_right, [1, 1, 2, 2], 0, 0),
  28.         (bisect_right, [1, 1, 2, 2], 1, 2),
  29.         (bisect_right, [1, 1, 2, 2], 1.5, 2),
  30.         (bisect_right, [1, 1, 2, 2], 2, 4),
  31.         (bisect_right, [1, 1, 2, 2], 3, 4),
  32.         (bisect_right, [1, 2, 3], 0, 0),
  33.         (bisect_right, [1, 2, 3], 1, 1),
  34.         (bisect_right, [1, 2, 3], 1.5, 1),
  35.         (bisect_right, [1, 2, 3], 2, 2),
  36.         (bisect_right, [1, 2, 3], 2.5, 2),
  37.         (bisect_right, [1, 2, 3], 3, 3),
  38.         (bisect_right, [1, 2, 3], 4, 3),
  39.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  40.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 1),
  41.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  42.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 3),
  43.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  44.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 6),
  45.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  46.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 10),
  47.         (bisect_right, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10),
  48.  
  49.         (bisect_left, [], 1, 0),
  50.         (bisect_left, [1], 0, 0),
  51.         (bisect_left, [1], 1, 0),
  52.         (bisect_left, [1], 2, 1),
  53.         (bisect_left, [1, 1], 0, 0),
  54.         (bisect_left, [1, 1], 1, 0),
  55.         (bisect_left, [1, 1], 2, 2),
  56.         (bisect_left, [1, 1, 1], 0, 0),
  57.         (bisect_left, [1, 1, 1], 1, 0),
  58.         (bisect_left, [1, 1, 1], 2, 3),
  59.         (bisect_left, [1, 1, 1, 1], 0, 0),
  60.         (bisect_left, [1, 1, 1, 1], 1, 0),
  61.         (bisect_left, [1, 1, 1, 1], 2, 4),
  62.         (bisect_left, [1, 2], 0, 0),
  63.         (bisect_left, [1, 2], 1, 0),
  64.         (bisect_left, [1, 2], 1.5, 1),
  65.         (bisect_left, [1, 2], 2, 1),
  66.         (bisect_left, [1, 2], 3, 2),
  67.         (bisect_left, [1, 1, 2, 2], 0, 0),
  68.         (bisect_left, [1, 1, 2, 2], 1, 0),
  69.         (bisect_left, [1, 1, 2, 2], 1.5, 2),
  70.         (bisect_left, [1, 1, 2, 2], 2, 2),
  71.         (bisect_left, [1, 1, 2, 2], 3, 4),
  72.         (bisect_left, [1, 2, 3], 0, 0),
  73.         (bisect_left, [1, 2, 3], 1, 0),
  74.         (bisect_left, [1, 2, 3], 1.5, 1),
  75.         (bisect_left, [1, 2, 3], 2, 1),
  76.         (bisect_left, [1, 2, 3], 2.5, 2),
  77.         (bisect_left, [1, 2, 3], 3, 2),
  78.         (bisect_left, [1, 2, 3], 4, 3),
  79.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 0, 0),
  80.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1, 0),
  81.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 1.5, 1),
  82.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2, 1),
  83.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 2.5, 3),
  84.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, 3),
  85.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3.5, 6),
  86.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4, 6),
  87.         (bisect_left, [1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 5, 10)
  88.     ]
  89.  
  90.     def test_precomputed(self):
  91.         for func, data, elem, expected in self.precomputedCases:
  92.             self.assertEqual(func(data, elem), expected)
  93.             self.assertEqual(func(UserList(data), elem), expected)
  94.  
  95.     def test_random(self, n=25):
  96.         from random import randrange
  97.         for i in xrange(n):
  98.             data = [randrange(0, n, 2) for j in xrange(i)]
  99.             data.sort()
  100.             elem = randrange(-1, n+1)
  101.             ip = bisect_left(data, elem)
  102.             if ip < len(data):
  103.                 self.failUnless(elem <= data[ip])
  104.             if ip > 0:
  105.                 self.failUnless(data[ip-1] < elem)
  106.             ip = bisect_right(data, elem)
  107.             if ip < len(data):
  108.                 self.failUnless(elem < data[ip])
  109.             if ip > 0:
  110.                 self.failUnless(data[ip-1] <= elem)
  111.  
  112.     def test_optionalSlicing(self):
  113.         for func, data, elem, expected in self.precomputedCases:
  114.             for lo in xrange(4):
  115.                 lo = min(len(data), lo)
  116.                 for hi in xrange(3,8):
  117.                     hi = min(len(data), hi)
  118.                     ip = func(data, elem, lo, hi)
  119.                     self.failUnless(lo <= ip <= hi)
  120.                     if func is bisect_left and ip < hi:
  121.                         self.failUnless(elem <= data[ip])
  122.                     if func is bisect_left and ip > lo:
  123.                         self.failUnless(data[ip-1] < elem)
  124.                     if func is bisect_right and ip < hi:
  125.                         self.failUnless(elem < data[ip])
  126.                     if func is bisect_right and ip > lo:
  127.                         self.failUnless(data[ip-1] <= elem)
  128.                     self.assertEqual(ip, max(lo, min(hi, expected)))
  129.  
  130.     def test_backcompatibility(self):
  131.         self.assertEqual(bisect, bisect_right)
  132.  
  133. #==============================================================================
  134.  
  135. class TestInsort(unittest.TestCase):
  136.  
  137.     def test_vsBuiltinSort(self, n=500):
  138.         from random import choice
  139.         for insorted in (list(), UserList()):
  140.             for i in xrange(n):
  141.                 digit = choice("0123456789")
  142.                 if digit in "02468":
  143.                     f = insort_left
  144.                 else:
  145.                     f = insort_right
  146.                 f(insorted, digit)
  147.         self.assertEqual(sorted(insorted), insorted)
  148.  
  149.     def test_backcompatibility(self):
  150.         self.assertEqual(insort, insort_right)
  151.  
  152. #==============================================================================
  153.  
  154.  
  155. class LenOnly:
  156.     "Dummy sequence class defining __len__ but not __getitem__."
  157.     def __len__(self):
  158.         return 10
  159.  
  160. class GetOnly:
  161.     "Dummy sequence class defining __getitem__ but not __len__."
  162.     def __getitem__(self, ndx):
  163.         return 10
  164.  
  165. class CmpErr:
  166.     "Dummy element that always raises an error during comparison"
  167.     def __cmp__(self, other):
  168.         raise ZeroDivisionError
  169.  
  170. class TestErrorHandling(unittest.TestCase):
  171.  
  172.     def test_non_sequence(self):
  173.         for f in (bisect_left, bisect_right, insort_left, insort_right):
  174.             self.assertRaises(TypeError, f, 10, 10)
  175.  
  176.     def test_len_only(self):
  177.         for f in (bisect_left, bisect_right, insort_left, insort_right):
  178.             self.assertRaises(AttributeError, f, LenOnly(), 10)
  179.  
  180.     def test_get_only(self):
  181.         for f in (bisect_left, bisect_right, insort_left, insort_right):
  182.             self.assertRaises(AttributeError, f, GetOnly(), 10)
  183.  
  184.     def test_cmp_err(self):
  185.         seq = [CmpErr(), CmpErr(), CmpErr()]
  186.         for f in (bisect_left, bisect_right, insort_left, insort_right):
  187.             self.assertRaises(ZeroDivisionError, f, seq, 10)
  188.  
  189.     def test_arg_parsing(self):
  190.         for f in (bisect_left, bisect_right, insort_left, insort_right):
  191.             self.assertRaises(TypeError, f, 10)
  192.  
  193. #==============================================================================
  194.  
  195. libreftest = """
  196. Example from the Library Reference:  Doc/lib/libbisect.tex
  197.  
  198. The bisect() function is generally useful for categorizing numeric data.
  199. This example uses bisect() to look up a letter grade for an exam total
  200. (say) based on a set of ordered numeric breakpoints: 85 and up is an `A',
  201. 75..84 is a `B', etc.
  202.  
  203.     >>> grades = "FEDCBA"
  204.     >>> breakpoints = [30, 44, 66, 75, 85]
  205.     >>> from bisect import bisect
  206.     >>> def grade(total):
  207.     ...           return grades[bisect(breakpoints, total)]
  208.     ...
  209.     >>> grade(66)
  210.     'C'
  211.     >>> map(grade, [33, 99, 77, 44, 12, 88])
  212.     ['E', 'A', 'B', 'D', 'F', 'A']
  213.  
  214. """
  215.  
  216. #------------------------------------------------------------------------------
  217.  
  218. __test__ = {'libreftest' : libreftest}
  219.  
  220. def test_main(verbose=None):
  221.     from test import test_bisect
  222.     from types import BuiltinFunctionType
  223.     import sys
  224.  
  225.     test_classes = [TestBisect, TestInsort]
  226.     if isinstance(bisect_left, BuiltinFunctionType):
  227.         test_classes.append(TestErrorHandling)
  228.  
  229.     test_support.run_unittest(*test_classes)
  230.     test_support.run_doctest(test_bisect, verbose)
  231.  
  232.     # verify reference counting
  233.     if verbose and hasattr(sys, "gettotalrefcount"):
  234.         import gc
  235.         counts = [None] * 5
  236.         for i in xrange(len(counts)):
  237.             test_support.run_unittest(*test_classes)
  238.             gc.collect()
  239.             counts[i] = sys.gettotalrefcount()
  240.         print counts
  241.  
  242. if __name__ == "__main__":
  243.     test_main(verbose=True)
  244.